noip2012提高组初赛（答案+选择题题目+个人分析）

 一、单项选择题（共10题，每题1.5分，共计15分；每题有且仅有一个正确选项）  

 1．目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。 A．硅     B．铜    C．锗     D．铝

A

送分题

 2．（    ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。  A．资源管理器   B．浏览器   C．电子邮件   D．编译器

B

显然=w=

 3．目前个人电脑的（     ）市场占有率最靠前的厂商包括Intel、AMD等公司。

 A．显示器   B．CPU   C．内存    D．鼠标

B

英特尔公司是美国一家主要以研制CPU处理器的公司，是全球最大的个人计算机零件和CPU制造商，它成立于1968年，具有46年产品创新和市场领导的历史。1971年，英特尔推出了全球第一个微处理器

 4．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（    ）。

 A． 中国公司的经理与波兰公司的经理交互商业文件

  B． 军队发布命令

  C． 国际会议中，每个人都与他国地位对等的人直接进行会谈

  D． 体育比赛中，每一级比赛的优胜者晋级上一级比赛

A

图图依旧没有贴上来...网络分层

OSI模型有7层结构，每层都可以有几个子层。OSI的7层从上到下分别是7应用层6表示层5会话层4传输层3网络层2数据链路层1物理层

 

  5．如里不在快速排序中引入随机化，有可能导致的后果是（    ）。

 A．数组访问越界   B．陷入死循环  C．排序结果错误       D．排序时间退化为平方级

D

常识吧=w=

 6．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（    ）计算机。  

A．电子管   B．晶体管   C．集成电路   D．超大规模集成电路  

A

显然A，ENIAC是世界上第一台通用计算机，也是继ABC（阿塔纳索夫-贝瑞计算机）之后的第二台电子计算机。当然是电子管

 7．在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

A．系统分配的栈空间溢出     B．系统分配的堆空间溢出

 C．系统分配的队列空间溢出    D．系统分配的链表空间溢出  

A

被报过错的人都知道=w=，学过递归的都知道=w=（递归用的是栈）

 8．地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（      ）。  A．128KB    B．1MB   C．1GB    D．4GB

D

然而我并不会=。=

地址总线 (Address Bus；又称：位址总线)属于一种电脑总线 （一部份），是由CPU或有DMA能力的单元，用来沟通这些单元想要存取（读取/写入）电脑内存元件/地方的实体位址。

数据总线的宽度，随可寻址的内存组件大小而变，决定有多少的内存可以被访问。取个例子，一个16位宽度的地址总线（通常在1970年和1980年早期的8位处理器中使用）到达2的16次方= 65536 = 64KB的内存地址，而一个32位地址总线（通常在像现今2004年的PC处理器中）可以寻址到4,294,967,296 = 4GiB的地址

9．以下不属于3G（第三代移动通信技术）标准的是（     ）。

A．GSM    B．TD-SCDMA  C．CDMA2000   D．WCDMA  

A

对于我个人来讲，这是一道拼人品的题。

第三代移动通信技术（3rd-generation，3G），是指支持高速数据传输的蜂窝移动通讯技术。3G服务能够同时传送声音及数据信息，速率一般在几百kbps以上。目前3G存在四种标准：CDMA2000，WCDMA，TD-SCDMA，WiMAX。

10．仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（    ）

 A．由研究蝙蝠，发明雷达     B．由研究蜘蛛网，发明因特网  C．由研究海豚，发明声纳     D．由研究电鱼，发明伏特电池

B

这个错的很明显了吧....

二、不定项选择题（共10题，每题1.5分，共计15分；每题有一个或多个正确选项，多选或少选均不得分）  

1、如果对于所有规模为n的输入，一个算法均恰好进行（     ）次运算，我们可以说该算法的时间复杂度为O（2^n） 。 A2^(n+1)+     B．3^n     C．n*2^n    D．2^2n   

A

显然=w=，（D多了一个平方）

 2． 从顶点0A出发，对有向图（    ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是A0，A1,A2，A3，A4

AD

学过bfs的水过就好

3．如果一个栈初始时为空，且当前栈中的元素从栈顶到栈底依次为a，b，c（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（     ）。

 A．a, b, c, d     B．b, a, c, d     C．a, c, b, d        D．d, a, b, c  

AD，显然

4．在计算机显示器所使用的RGB颜色模型中，（    ）属于三原色之一。

A．黄色    B．蓝色    C．紫色     D．绿色

BD

5、一棵二叉树一共有19个节点，其叶子节点可能有（    ）个。  

A．1    B．9   C10     D10.5 

ABC

最少一个，最多19-（19 div 2）=10个

 6．已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为d(u,v)。若v1v2v3v4v5 是图G上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（   ）。

 A．V1 到v2的最短路径可能包含一个环

B．D(v1,v2)=d(v2,v1)=   

C． D(v1,v3)<=d(v1,v2)+d(v2,v3)

D.如果v1->v2->v3->v4->v5是v1到v5的一条最短路径那么v2->v3->v4是v2到v4的最短路径

CD，没有什么可多说的，有环显然是不可以的，注意这是一个有向图

  

7．逻辑异或（Å）是一种二元运算，其真值表如下所示。 

以下关于逻辑异或的性质，正确的有（     ）。 

A．交换律Å=Å  

B．结合律：Å=ÅÅ 

C．关于逻辑与的分配律：

D．关于逻辑或的分配律：

AB

粘贴问题，原题自己百度一下吧

8．十进制下的无限循环小数（不包括循环节内的数字均为0成均为9的平凡情况），在二进制下有可能是（    ）。 

A．无限循环小数(不包括循环节内的数字均为0或均为9）   

B．无限不循环小数   

C．有限小数    

 D．整数 

A，显然

9．（     ）是目前互联网上常用的E-mail服务协议。

 A．HTTP    B．FTP    C．POP3  D．SMTP 

CD

常用的电子邮件协议有SMTP、POP3、IMAP4，它们都隶属于TCP/IP协议簇，默认状态下，分别通过TCP端口25、110和143建立连接

10．以下关于计算复杂度的说法中，正确的有（    ）。 

A．如果一个问题不存在多项式时间的算法，那它一定是NP类问题

 B．如果一个问题不存在多项式时间的算法，那它一定不是P类问题

 C．如果一个问题不存在多项式空间的算法，那它一定是NP类问题 

D．如果一个问题不存在多项式空间的算法，那它一定不是P类问题

BD

NP问题是指还未被证明是否存在多项式算法能够解决的问题，而其中NP完全问题又是最有可能不是P问题的问题类型。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题

P问题：P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出

三．问题求解

1.256

其实我是不会算的，然后大神告诉我：

对于每个p、q、r只能取真、假两种情况，共有八种组合，无论哪组组合都只有真假两种结果，所以两两不等价的个数有2^8种（别问我所以是怎么来的=。=）

2、5536

其实我还是不会做=。=

题解大人告诉我：这是一道动规题，所以永远不要把初赛想得多么白痴=。=，

F[i]:=g[i,0]+g[i,1](f[i]表示以i为根节点的独立集个数，1表示选，0表示不选）；

显然两两不相邻，所以选根节点时，两个子节点不能选；不选根节点时，直接是左右儿子相乘（根据计数原理可得）

即:g[i,0]:=f[left[i]]*f[right[i]];

   G[i,1]:=g[left[i],0]*g[right[i],0];

从下往上编号，这样根节点编号即为节点总数，求出f[17]即可；

【题解大人您腿上缺挂件么】

四．阅读程序写结果

1、41（还是送分题，看清循环范围即可）

2/16（当看都gcd的时候就应该明白了一切）

3、（1）7；（2）2004

第一组推一下应该都没问题，至于第二组，我是找规律的

4、55（我看不下去了=A=）

五．完善程序

【pascal答案】

1、

(1)False

(2)Uesd[date[i]]:=false

(3)j

(4)n

(5)Break

2、

（1）next:=(k mod c)+1;

（2）s[n]:=q[tail];

（3）Q[head]

（4）Q[headl]

（5）P[tail]

（6）Next(head)

                ——by Eirlys

转载请注明出处=w=